package com.dmzc.sort;

/**
 * 归并排序,将大的问题进行分解，然后递归求解
 */
public class MergeSort {
    public static void main(String[] args) {
        Node1[] node1s = new Node1[5];
        node1s[0] = new Node1(2, 1);
        node1s[1] = new Node1(3, 2);
        node1s[2] = new Node1(6, 3);
        node1s[3] = new Node1(1, 4);
        node1s[4] = new Node1(7, 5);
        merge_sort(node1s, 0, node1s.length - 1);
        for (int i = 0; i < node1s.length; i++) {
            System.out.println(node1s[i]);
        }
    }


    public static void merge_sort(Node1[] A, int p, int r) {
        if (p >= r) return;
        int q = p + (r - p) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        //对分治的问题解决后，合并数组
        merge(A, p, q, r);
    }

    private static void merge(Node1[] A, int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int k = 0;
        Node1[] tmp = new Node1[r - p + 1];
        while (i <= q && j <= r) {
            if (A[i].index <= A[j].index) {
                tmp[k++] = A[i++];
            } else {
                tmp[k++] = A[j++];
            }
        }
        int start = i;
        int end = q;
        if (j <= r) {
            start = j;
            end = r;
        }
        while (start <= end) {
            tmp[k++] = A[start++];
        }
        for (i = 0; i < r - p; ++i) {
            A[p + i] = tmp[i];
        }
    }
}

